/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 16
 * Time: 15:14
 */
//牛客 最长公共子串
public class Solution3 {
    public String LCS (String str1, String str2) {
        int max = 0;
        int pos = 0;
        int m = str1.length(), n = str2.length();
        //dp[i][j]表示在s1中前i个字符与s2中前j个字符的最长公共子串
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <=n ; j++) {
                if(str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else {
                    dp[i][j] = 0;//重点，因为这是子串，必须连续相等，断开要重新开始
                }
                if (dp[i][j] > max) {//每遍历一次就更新一次最大值
                    max = dp[i][j];
                    pos = i - 1;
                }
            }
        }
        return str1.substring(pos - max + 1, pos + 1);
    }
}
